<html>
<head>
<title>The lightest language</title>
</head>

<body>

<center>
<h1>POI V Stage 3 Problem 4</h1>
<h1>The lightest language</h1>
</center>

<P>
Alphabet A<SUB>k</SUB> consists of k initial letters of English
alphabet. A positive integer called a weight is
assigned to each letter of the alphabet. A weight of a word
built from the letters of the alphabet A<SUB>k</SUB> is the sum
of weights of all letters in this word.
A language over an alphabet A<SUB>k</SUB> is any finite set of
words built from the letters of this alphabet.
A weight of a language is the sum of weights of all its words.
We say that the language is prefixless
if for each pair of different words w, v from this language w is not a prefix of v.

</P>
<P>
We want to find out what is the minimal possible weight of an n-element,
prefixless language over an alphabet A<SUB>k</SUB>.
</P>

<h2>Example</h2>

<P>
Assume that k = 2 , the weight of the letter a - W(a)=2 and
the weight of the letter b - W(b) = 5.
The weight of the word ab - W(ab)= 2+5=7.
W(aba)=2+5+2=9.
The weight of the language J = {ab, aba, b} - W(J)  = 21.
The language J is not prefixless, since the word ab is
a prefix of aba.

The lightest tree-element, prefixless language over the alphabet
A<SUB>2</SUB>  (assuming that weights of the letters are as before)
is {b, aa, ab}; its weight is 16.
</P>

<h2>Task</h2>

<P>
Write a program that:
<UL>
<LI>reads  two integers n, k and the weights of k letters of 
an alphabet
A<SUB>k</SUB> from the text file NAJ.IN;
<LI>computes the minimal weight of a prefixless, n-element
language over the alphabet A<SUB>k</SUB>;
<LI>writes the result to the text file NAJ.OUT.
</UL>
</P>

<h2>Input</h2>

<P>
In the first line of the input file NAJ.IN there are two
positive integers n and k separated by a single space,
(2&lt;=n&lt;=10000,
2&lt;=k&lt;=26).
These are the number of words in a language and the number of
letters in an alphabet respectively.
The second line contains k positive integers separated by single spaces. Each of them is
not greater than 10000. The i-th number is the weight of the
i-th letter.
</P>

<h2>Output</h2>
<P>
In the first and only line of the output file NAJ.OUT
there should be written one integer - the weight of
the lightest prefixless n-element language over the alphabet
A<SUB>k</SUB>.
</P>

<h2>Sample Input</h2>
<PRE>
3 2
2 5
</PRE>

<h2>Sample Output</h2>
<PRE>
16
</PRE>

</body>

</html>
